<?php
/**
 * <https://y.st./>
 * Copyright © 2017 Alex Yst <mailto:copyright@y.st>
 * 
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program. If not, see <https://www.gnu.org./licenses/>.
**/

$xhtml = array(
	'<{title}>' => 'Machine learning for automated shops in computer games',
	'takedown' => '2017-11-01',
	'<{body}>' => <<<END
<img src="/img/CC_BY-SA_4.0/y.st./weblog/2017/10/01.jpg" alt="My entryway and part of my storage room" class="framed-centred-image" width="800" height="480"/>
<section id="general">
	<h2>General news</h2>
	<p>
		Work today was mostly mindless, so I tried to come up with more of the base bonuses for <code>minequest</code>.
		I was unsuccessful at that, instead coming up with an improvement for an existing bonus I hadn&apos;t been aware needed improvement.
		Later, I came up with an idea for a bonus that is essentially just the shop mod I&apos;ve wanted to build for quite a while, but haven&apos;t been able to figure out how to.
		It doesn&apos;t belong crammed into one of the bonuses for Minetest Game items though.
		It deserves its own mod, so I started thinking about how to implement that again.
	</p>
	<p>
		The problem is that the defining characteristic of my shop mod is that it will use a supply-and-demand-based algorithm to decide the prices for all available items.
		(Today, I decided to make any item that doesn&apos;t drop itself unbuyable, as well as any node that isn&apos;t digable or is only digable via a digging group for which there is no available tool, but that&apos;s irrelevant to the problem.
		Players acquire money by selling stuff they own at the shop, and they can buy whatever else they like there.
		Players can set up their own shops for selling to each other, but the initial money will need to come from transactions with the server itself.
		Players will set their own prices for their own shops, but the automated shops run by the server will change their prices based on how many of each item is bought and sold.
		Common items that are sold to the server more than they are bought from it will be worth very little, while rare items that only ever get bought from the server, never sold to it, will be incredibly expensive.
		But how do I get such an algorithm to work?
		That&apos;s the part that always stumps me.
		I thought I had a solution today, but the solution didn&apos;t take into account proportionality like it should.
		If an item is sold twice as often as another, it should be worth half as much.
		The advantage of the algorithm I came up with though was that both positive (more sales to the server) and negative numbers (more purchases from the server) were handled consistently.
		Even the base case of zero worked out fine.
		The next solution I came up with seemed to work at first, but actually caused items that had been bought by players more times than sold (the most valuable items) cost a negative amount of money.
		I&apos;m not convinced prices of any of the items had the right proportionality, either.
		On the way home, I came up with a third solution.
		I think it&apos;s the most promising yet, but it still has a divide-by-zero base case and negative prices for valuable items.
		Still, the prices on everything that doesn&apos;t have a negative price has exactly the price I&apos;d want it to.
		That&apos;s mostly because I spent time shifting numbers around in my head trying to find exactly would would provide the proportional pricing I sought.
		If I can fix the negative pricing issue, I can probably apply that same solution to fix the division by zero as well.
	</p>
	<p>
		It took me all day to realise why this problem&apos;s been baffling me all this time, but I finally figured it out: this is a machine learning problem!
		I don&apos;t know what prices everything should have to be fair.
		I&apos;m trying to get the machine to figure out the prices itself based on user behaviour.
		Machine learning is no easy branch of computer science to work in.
		It might take a genius to solve the issue I keep banging my head against.
		Of course, that only makes me want to solve the problem even more.
		Obviously, if I solve this problem, it doesn&apos;t actually make me a genius.
		After all, I usually don&apos;t do anything nearly this intellectual.
		Still, it&apos;ll make me feel pretty darn awesome if I can actually make this personal breakthrough.
	</p>
</section>
<section id="dreams">
	<h2>Dream journal</h2>
	<p>
		I don&apos;[t remember much of my dream; the main thing I remember was that it was mixed up, and possibly incoherent.
		It might&apos;ve also involved my paper shredder being broken.
	</p>
</section>
<section id="university">
	<h2>University life</h2>
	<p>
		I wrote up my discussion post on processor scheduling:
	</p>
	<blockquote>
		<h3>Single-queue scheduling</h3>
		<p>
			Single-queue scheduling is like the single-processor scheduling we discussed last week, but adapted to work with multiple processors.
			That means that this single &quot;queue&quot; could be made up of several smaller queues of differing priority level, as in a multi-level feedback queue.
			Instead of the operating system selecting one of the highest-priority jobs to run though, it selects two (or more), one for each processor.
			However, two main problems exist in this setup.
			First is the issue of the queue locks.
			When a job is being sent to a processor, the queue needs to be locked so the same job doesn&apos;t get run by two processors at once.
			This causes the system to have to wait, so $a[CPU] time is wasted.
			The other issue is that a single process will likely end up on different processors during its lifespan.
			To be most efficient, a process should be run only on one processor, as to make the best use of that processor&apos;s cache.
			Otherwise, several caches will be used (one for each processor the process runs on), so more queries on the main memory will be made than necessary, not to mention that more effort will need to be put into maintaining cache coherency.
			It&apos;s possible to build a processor affinity mechanism into the queue, but it can be complex to do so and still results in some jobs bouncing between processors, even if others don&apos;t.
		</p>
		<h3>Multi-queue scheduling</h3>
		<p>
			Another option is to have one &quot;queue&quot; per processor.
			Again, each &quot;queue&quot; can be (but doesn&apos;t have to be) made up of several queues, differing in priority level.
			When a process is created, it is added to the queue of one of the processors, but none of the other queues.
			That way, every process is run on only one processor, and is dealing with only one cache.
			Lost $a[CPU] time due to locks is avoided, and caches are used more efficiently.
			However, even this system has its flaws.One $a[CPU] may end up with more processes than another, resulting in load imbalance.
			Processes in the less-populated queues will get more $a[CPU] time than those in more-populated queues.
			Even worse, one queue may run out of processes while there are still jobs to be done on other processors, resulting in underutilisation of resources.
			Both problems can be fixed by migrating jobs around between queues, but in the process, some cache efficiency of multi-queue scheduling is lost.
		</p>
		<div class="APA_references">
			<h3>References:</h3>
			<p>
				Arpaci-Dusseau, R. H., &amp; Arpaci-Dusseau, A. C. (2016, July 20). Multiprocessor Scheduling (Advanced). Retrieved from <a href="http://pages.cs.wisc.edu/~remzi/OSTEP/cpu-sched-multi.pdf"><code>http://pages.cs.wisc.edu/~remzi/OSTEP/cpu-sched-multi.pdf</code></a>
			</p>
		</div>
	</blockquote>
</section>
END
);
